1. Field of the Invention
The present invention relates generally to memory devices, and more particularly to content addressable memory devices that can be searched in variable data width.
2. Description of the Related Art
Memory devices are indispensable components of modern computer systems and networks. As storage devices, they are used to provide fast access to data and instructions stored therein. Content addressable memory (CAM) is a special type of memory that is often used for performing address searches. For example, Internet routers often include a CAM for searching the address of specified data. The use of CAMs allows the routers to perform fast searches to allow computer systems to communicate data with one another over networks. In addition, CAMs are also utilized in numerous other areas such as database searches, image processing, and voice recognition applications, where fast search performance is desired.
As is well known, CAMs typically include a two-dimensional row and column content addressable memory array of core cells, such that each row contains an address, pointer, or bit pattern entry. Within such an array of cells, a CAM may perform xe2x80x9creadxe2x80x9d and xe2x80x9cwritexe2x80x9d operations at specific addresses like a conventional random access memory (RAM). In addition, the CAM is also used to perform fast search operations that simultaneously compare a bit pattern of data against an entire list (e.g., column) of pre-stored entries (e.g., rows) of bit patterns in the CAM array. Based on these comparisons, the CAM typically outputs a result in the form of an address, pointer, or bit pattern corresponding to an entry that matches the input data. By thus performing comparisons simultaneously of all CAM entries, the CAM provides significant savings in search time over RAMs such as dynamic RAMs (DRAMs), static RAMs (SRAMs), and the like.
In modern computer systems and networks, CAMs are often used in various applications having different data size requirements. In Internet routers and switches, for example, a CAM may be used in medium access control (MAC) level switching, asynchronous transfer mode (ATM), and various network layer protocols such as Internet protocol (IP) versions 4 (Ipv4), 6 (Ipv6), and the like. As is well known in the art, the ATM often uses 32-bit data fields while the MAC level 2 addressing typically uses 48 to 64-bit data sizes. The data sizes may vary further depending on specific applications. For example, the 64-bit data size for the MAC level addressing may be increased to 128 bits when both the source and destination addresses are used in switching.
To address such varying data size requirements, one conventional approach has employed a CAM chip with a multitude of macros, each of which is configurable to a specific data size requirement. FIG. 1A shows a block diagram of a conventional CAM chip 100 having four macros 102, 104, 106, and 108. Each of the macros 102, 104, 106, and 108 is configurable by a user to specified widths for various applications. For example, the macro 102 is configured as a 4Kxc3x9764 block (i.e., 4K entries of 64 bit data width); the macros 104 and 108 are configured as an 8Kxc3x9732 block (i.e., 8K entries of 32 bit data width); and the macro 106 is configured as a 2Kxc3x97128 block (i.e., 2K entries of 128 bit data width). Thus, in this arrangement, all entries in a single macro have the same width.
FIG. 1B illustrates a block diagram of a macro 120 depicting various widths into which it can be configured. As shown, the macro 120 includes a plurality of blocks 122, 124, 126, 128, and 130, which can be configured into 32-bit width, 64-bit width, 128-bit width, or 256-bit width. For example, each of the blocks 122, 124, 126, and 128 may be used to provide 32-bit width. Alternatively, blocks 122 and 124 may be used to provide data width size of 64 bits.
Unfortunately, however, the width of conventional macros 102, 104, 106, 108, and 120 is typically configurable on the block level only using associated registers that specify data size for each of the macros. This means that each of the macros 102, 104, 106, 108, and 120 cannot accommodate more than one data size at the same time. The configuration of macros at the block level often results in wasting of valuable memory space. For example, if the macro 120 can accommodate 128 bit data width but is actually configured into 64 bit data width, half of the memory space will not be used, thus resulting effectively in the waste of 50% of memory space. Likewise, if the macro 120 can support up to 64-bit data width but is configured into 32-bit data size, half of the memory space will be lost. In addition, the use of macros generally requires the users or customers to be intimately knowledgeable about the macros and their data sizes to avoid overflow of the macros. Furthermore, if the macros are reprogrammed to different data sizes, valuable data (e.g., search statistics) could be lost in the process.
Thus, what is needed is a CAM device that can store variable data size widths for searching variable width data without wasting valuable memory space, thereby maximizing the usage of CAM space with attendant savings in cost.
The present invention fills these needs by providing variable width CAM devices for searching data of variable widths. It should be appreciated that the present invention can be implemented in numerous ways, including as a process, an apparatus, a system, a device, or a method. Several embodiments of the present invention are described below.
In one embodiment, the present invention provides a variable width CAM device for searching data of variable widths. The CAM device includes a plurality of CAM blocks and a plurality of dual-mode first encoders. The plurality of CAM blocks is configured to store a plurality of data of variable widths with each data having one or more data portions of one or more predetermined widths. Each CAM block is configured to store a predetermined width portion of the data such that each data is stored in one or more CAM blocks. The CAM blocks receive a search data having a specified number of search data portions with each search data portion having one or more predetermined widths. Each CAM block receives a search data portion of the search data for searching the search data in the CAM blocks. The plurality of dual mode first encoders is configured for concatenating the specified number of the CAM blocks to generate one or more search results. A set of the dual mode first encoders concatenates the specified number of CAM blocks to match the width of the search data. The remaining dual mode first encoders generate one or more search results when the concatenated CAM blocks contain data that matches the search data.
In another embodiment, the present invention provides a variable width CAM device including a plurality of CAM blocks and a plurality of first encoders. The plurality of CAM blocks is configured for storing a plurality of data having a plurality of widths. Each CAM block has a plurality of entries with each entry being configured to store a predetermined width data portion of one of the plurality of data. Each of the plurality of data is stored in one or more entries that are located in different CAM blocks. The CAM blocks are arranged to receive a search data having a specified number of search data portions such that each CAM block receives one search data portion having the predetermined width. Each entry in the CAM blocks is capable of generating a match result when the predetermined width data portion in each entry matches the search data portion of the predetermined width. The plurality of first encoders is configured to sequentially couple the plurality of CAM blocks in the specified number to match the width of the search data. Each first encoder is associated with one CAM block for receiving the match results from the entries in the associated CAM block. A set of the first encoders transmits the match results from the associated CAM blocks to next sequentially coupled CAM blocks as inputs. Each of the remaining first encoders generates a search result when the sequentially coupled CAM blocks contain data that matches the search data.
In yet another embodiment, a variable width CAM device is disclosed. The variable width CAM includes a plurality of CAM blocks, a plurality of first encoders, and a second encoder. The plurality of CAM blocks is arranged for storing data of variable widths with each CAM block having a plurality of entries. Each entry is configured to store data of a first width. Each CAM block is arranged to receive a first width search data portion of a search data for input to each entry in each CAM block. Each entry in the CAM blocks is capable of generating a match result when the data in each entry matches the search data portion of the first width. The plurality of first encoders is configured to concatenate the entries of the plurality of CAM blocks. Each first encoder is associated with one CAM block for receiving the match results from the entries in the associated CAM block. Each first encoder is arranged to transmit the match results to a next sequentially coupled CAM block as inputs to the entries in the next CAM block. A set of the first encoders is adapted to transmit the match results for concatenating the entries in one or more CAM blocks to match the width of the concatenated entries and the search data. Each of the remaining first encoders generates a search result in response to match results of the concatenated entries. The second encoder is coupled to the plurality of first encoders to receive one or more search results. The second encoder selects one of the received search results for output.
By storing data of variable widths for searching variable width data, the CAM devices of the present invention provide savings in CAM space and enhanced flexibility. For example, the variable width storage and searching of the data provides substantial flexibility to users by allowing the tag bits, which identify the width of an entry, to be programmed on an entry basis instead of block basis. In addition, the storage and searching of variable width data on individual entry basis saves valuable CAM space by eliminating unused or unusable CAM spaces associated with conventional CAM macros. The CAM devices with the variable width storage and searching capabilities are particularly beneficial in multi-protocol applications such as IPv4, IPv6, ATM, MAC level switching, etc. Other advantages of the invention will become apparent from the following detailed description, taken in conjunction with the accompanying drawings, illustrating by way of example the principles of the invention.